class Solution {
public:
    int uniquePaths(int m, int n) {
        // 二维数组动态规划
        // dp[i][j]表示到达当前位置的路径总数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[1][1] = 1;   // 初始化
        
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1)
                    continue;
                // 当前位置取决于上方和左方的路径数和
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
};